//
// Created by 子夜求知 on 2022/9/15.
// 常用排序算法

#ifndef TREEPROJECT_USUALSORT_H
#define TREEPROJECT_USUALSORT_H
#include "LinkList.h"


/**
 * 插入排序:（基于数组的实现方式）
 * @param A
 * @param n
 */
void InsertSort(int A[],int n){
    int i,j;
    for (i = 2; i <= n ; i++) {     // 依此将A[2]~A[n]插入前面已经排序序列
        if(A[i]<A[i-1]){            // 若A[i]关键代码小于其前驱，将A[i]插入有序表
            A[0] = A[i];            // 复制为哨兵，A[0]不存放元素
            int j;
            for (j = i-1; A[0]<A[j] ; --j)  // 从后往前查找待插入位置，边界条件：A[0]<A[j]
                A[j+1] = A[j];      // 向后挪位
            A[j+1] = A[0];          // 复制到插入位置
        }
    }
}

/**
 * 基于链表的直接插入排序
 *  head为哨兵结点,head节点的下一个结点才为数据结点
 * @param head
 *   (1）算法思想： 每次将⼀个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插⼊完成。 时间复杂度O(n^2)
    （2）实现步骤：
        1、整个排序过程为n-1趟插入，
        2、先将序列中第1个记录看成是一个有序子序列，
        3、然后从第2个记录开始，逐个进行插入，直至整个序列有序。
 */
void straightInsertSort(linklist head){
   if(head->next==NULL)
       return;
   linknode *sorted = head->next;   // sorted为已排序完成序列的最后的一个结点
   linknode *cur = sorted->next;    // cur为待排序结点
   while (cur!=NULL){
        if(sorted->data<=cur->data){
            sorted = sorted->next;
        } else{
            linknode *pre = head;    // pre为后续寻找比待排序结点更小的结点的遍历结点
            while (pre->next->data<=cur->data){ // pre指针向后遍历寻找小于待排序结点的最后一个结点
                pre = pre->next;
            }
            /*下面三行代码的解释：
             * 找到最后一个小于待排序结点(pre)之后：
             * 1、已排序列表向后移动一位：sorted->next = cur->next;
             * 2、将待排序结点(cur)插入到(pre)结点之后： cur->next = pre->next;
             * 3、将pre结点指向cur结点：pre->next = cur;
             */
            sorted->next = cur->next;
            cur->next = pre->next;
            pre->next = cur;
        }
       cur = sorted->next;  // 待排序结点为已排序列表最后一个结点的后一位(sorted->next)
   }
}

/**
 * 基于数组的快速排序
 * @param array
 * 数组第一个数据元素为下标 1，不是0
 */
void quickSort(int array[]){
    int mid = array[1]; // 取第一个元素作为枢轴
    int low = 1;
    int high = sizeof (array)/sizeof (array);
    while (low<high){
        while (low<high&&array[high]>=mid) high--;
        array[low] = array[high];
        while (low<high&&array[low]<=mid) low++;
        array[high] = array[low];
    }
    array[low] = mid;
}

/**
 * 基于数组的简单选择排序
 * @param A
 * @param n
 */
void SelectSort(int A[],int n){
    int i;
    for (i = 0; i < n-1; i++) {
        int min = i;
        for (int j = i+1; j < n; j++)
            if(A[j]<A[min])
                min = j;
        if(min!=i){ // 交换为更小的元素
            int p = A[i];
            A[i] = A[min];
            A[min] = p;
        }
    }
}

/**
 * 基于链式结构上实现简单选择排序算法
 * @param head
 */
void SelectLinkListSort(linklist head){
    linklist p,q,s;
    int min,t;
    if(head==0 || head->next==0)
    {
        return;
    }
    // q指向已排序部分列表的后一个元素，并且假设为min值
    for(q=head;q!=0;q=q->next)
    {
        min=q->data;
        // s始终指向当前找到的最小的结点
        s=q;
        for(p=q->next;p!=0;p=p->next)   // p遍历链表，并且不断的与min进行对比，修改
        {
            if(min>p->data)     // 发现比min更小的值，立刻修改min的值为当前p指针指向的结点的值
            {
                min=p->data;
                s=p;            // s指向当前数值最小的结点
            }
        }
        if(s!=q)        // 找到最小的结点之后，交换最小值结点和p当前指向结点的值(data)
        {
            t=s->data;
            s->data=q->data;
            q->data=t;
        }
    }
}

/**
 * 设计将所有奇数移到所有偶数之前的算法
 * @param nums
 * @param i
 * @param j
 */
void quickpass(int nums[],int i,int j){
    int t;
    while (i<j)
    {
        while (j>=0 && nums[j]%2==0)    // 从最后一个开始找，如果是偶数就不用动
        {
            j--;
        }
        while (i<j&&nums[i]%2==1){      // 从最前一个开始找，如果是奇数就不用动
            i++;
        }
        if(i<j){
            t = nums[j];
            nums[j] = nums[i];
            nums[i] = nums[j];
        }
    }
}

/**
 * 折半插入排序：low是需要插入的位置，所以当前的low和low之后的元素需要向后移动
 * while循环之后：low>high,并且 high+1=low
 * while循环之后的for循环，作用是将high+1到i-1部分的数据全部后移，将需要插入的数据放到数组指针为high+1的位置上
 * @param A
 * @param n
 */
void BineryInsertSort(int A[],int n){
    int i,j,low,high,mid;
    for (i = 2; i <=n ; ++i) {      // 依次将A[2]~A[n]插入前面的已排序序列
        A[0] = A[i];                // 将A[i]暂存到A[0]
        low = 1; high = i-1;        // 设置折半查找的范围
        while (low<high){           // 折半查找(默认递增有序)
            mid = (low+high)/2;     // 取中间点
            if(A[mid]>A[0])
                high = mid-1;        // 查找左半子表
            else
                low = mid+1;        // 查找右半子表
        }
        for (j = i-1; j >=high+1; --j)
            A[j+1] = A[j];      // 统一后移动元素，空出插入位置
        A[high+1] = A[0];       // 插入操作
    }
}

/**
 * 希尔排序：
 * 时间复杂度分析：该算法和增量序列选择有关，目前无法用数学手段证明确切的时间复杂度
 * 最坏的时间复杂度：O(n^2),当n在某个范围内时，可达O(n^1.3)
 * @param A
 * @param n
 */
void ShellSort(int A[],int n){
    int d,i,j;
    // A[0] 只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for (int d = n/2; d >=1 ; d = d/2) {    // 步长变化
        for (i = d+1;i<=n;i++) {
            if(A[i]<A[i-d]){       // 需将A[i]插入有序增量子表
                A[0] = A[i];       // 暂存在A[0]
                for (j = i-d; j>0 && A[0]>A[j] ; j-=d)
                    A[j+d] = A[j];  // 记录后移，查找插入的位置
                A[j+d] = A[0];      // 插入
            }
        }
    }
}
#endif //TREEPROJECT_USUALSORT_H
